package algorithm.array;

/**
 * leetcode : https://leetcode.com/problems/first-missing-positive/
 * Difficulty : Hard
 *
 * 给一个无序的数组，找出其中缺失的最小正整数
 *
 *
 * 参考答案：https://leetcode.com/problems/first-missing-positive/discuss/17083/O(1)-space-Java-Solution
 * 解析：
 * 关键在于使用swap（交换），交换数组中的元素，来保持使用常量的内存。
 * 由于是定长的数组，那么缺失的最大的数字，也就是本题的结果，只能在 [1,nums.length+1] 之间内。
 *
 * 具体解法是，把对应数字，找到其在数组中对应的位置。
 * 例如：数字1放到index=0，数字2放到index=1，数字7放到index=6（如果数组有这么长的话）
 * 这是个O(1) 操作
 *
 * 交换完成后，从头开始找，数字=index+1 则继续往后找
 * 找到不符合条件的那个index, 结果就是index+1
 *
 *
 * Created by yzy on 2019-09-03 15:48
 */

public class FirstMissingPositive {

    public static void main(String[] args) {
        int[] int_a1 = new int[]{1,2,0};
        int[] int_a2 = new int[]{3,4,-1,1};
        int[] int_a3 = new int[]{7,8,9,10,12};

        System.out.println(firstMissingPositive(int_a1));
        System.out.println(firstMissingPositive(int_a2));
        System.out.println(firstMissingPositive(int_a3));
    }

    /**
     * Runtime: 0ms, 100.0%
     * Memory: 34.6MB, 100.0%
     *
     *
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        int i=0;
        while(i < nums.length){
            if(i+1==nums[i] || nums[i]<=0 || nums[i]>nums.length) i++;
            else if(nums[nums[i]-1] != nums[i]) swap(nums, i, nums[i]-1);
            else i++;
        }
        i=0;
        while(i<nums.length && nums[i]==i+1) i++;
        return i+1;
    }

    private static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
